package me.shan.sort.heap;

import java.util.Arrays;

/**
 * @author liuchuang
 */
public class HeapSort {

    public static void sort(int[] array) {
        heapSort(array);
    }

    private static void heapSort(int[] array) {
        if (array == null || array.length < 2) {
            return;
        }
        // 先创建大根堆
        int heapSize = 0;
        for (int i = 0; i < array.length; i++) {
            heapInsert(array, i);
            heapSize++;
        }
        // 此时最大值已经在array[0]了，将array[0]放到数组最后，heapSize-1，最大值处理完成
        swap(array, 0, --heapSize);
        while (heapSize > 0) {
            // 对0位置做heapify，0位置就又会是最大值，继续将array[0]与heapSize-1交换，重复此过程
            heapify(array, 0, heapSize);
            swap(array, 0, --heapSize);
        }
    }

    /**
     * 大根堆插入
     * 如果插入的数比父节点数大，则将插入的数和父节点数交换，并继续比较上一层，直到不比父节点大或到了根节点位置
     * @param array 待插入数组
     * @param index 插入的位置
     */
    private static void heapInsert(int[] array, int index) {
        while (array[index] > array[(index - 1) / 2]) {
            swap(array, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    /**
     * 堆调整
     * 如果index位置的数比子节点中任一数小，则将index位置的数与子节点中较大的数交换，并继续比较下一层，直到不比子节点小或超过堆大小
     *
     * @param array    待处理数组
     * @param index    调整的位置
     * @param heapSize 堆的大小
     */
    private static void heapify(int[] array, int index, int heapSize) {
        int left = index * 2 + 1;
        while (left < heapSize) {
            int largest = (left + 1) < heapSize && array[left + 1] > array[left] ? left + 1 : left;
            largest = array[largest] > array[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(array, index, largest);
            index = largest;
            left = index * 2 + 1;
        }
    }

    private static void swap(int[] array, int a, int b) {
        if (a == b) {
            return;
        }
        array[a] = array[a] ^ array[b];
        array[b] = array[a] ^ array[b];
        array[a] = array[a] ^ array[b];
    }

    public static void main(String[] args) {
        int[] array = {-7, -54, -49, 35, -60};
        int[] temp = new int[array.length];
        System.arraycopy(array, 0, temp, 0, temp.length);
        sort(array);
        System.out.println(Arrays.toString(array));
        Arrays.sort(temp);
        System.out.println(Arrays.toString(temp));
    }
}
